#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

using namespace std;

namespace k_val {
	//节点信息
	template<class K, class V>
	class AVLNode {
	public:
		AVLNode(const pair<K, V>& kv)
			:_bf(0)
			,_kv(kv)
			, left(nullptr)
			, right(nullptr)
			,father(nullptr)
		{
			
		}
		int _bf;//平衡因子
		pair<K, V> _kv;
		AVLNode<K, V>* left;
		AVLNode<K, V>* right;
		AVLNode<K, V>* father;
	};


	template<class K, class V>
	class AVLTree {

		typedef AVLNode<K, V> Node;
		typedef Node* pNode;
	public:
		AVLTree()
			:_root(nullptr)
		{

		}

		//删除
		bool Erase(const K& key) {
			if (_root == nullptr)return false;
			if (!Find(key))return false;
			pNode cur = _root;
			pNode pa = _root;
			while (cur) {
				if (cur->_kv.first < key) {
					pa = cur;
					cur = cur->right;
				}
				else if (cur->_kv.first > key) {
					pa = cur;
					cur = cur->left;
				}
				else break;
			}

			//被删除的节点孩子有空
			if (cur->left == nullptr) {
				if (cur == _root) {//如果被删除的节点是头节点
					pNode t = _root;
					_root = cur->right;
					delete t;
				}
				else if (pa->_kv.first < cur->_kv.first) {
					pa->right = cur->right;
					delete cur;
				}
				else {
					pa->left = cur->right;
					delete cur;
				}

			}
			else if (cur->right == nullptr) {
				if (cur == _root) {//如果被删除的节点是头节点
					pNode t = _root;
					_root = cur->left;
					delete t;
				}
				else if (pa->_kv.first < cur->_kv.first) {
					pa->right = cur->left;
					delete cur;
				}
				else {
					pa->left = cur->left;
					delete cur;
				}

			}//cur的两个孩子节点都不为空
			else {
				pNode ffa = cur;
				pNode minright = cur->right;
				while (minright->left) {
					ffa = minright;
					minright = minright->left;
				}

				ffa->left = minright->right;
				std::swap(minright->_kv.first, cur->_kv.first);
				delete minright;
			}


		}


		//查找
		pNode Find(const K& key) {
			assert(_root != nullptr);
			pNode cur = _root;
			while (cur) {
				if (cur->_kv.first < key) {
					cur = cur->right;
				}
				else if (cur->_kv.first > key) {
					cur = cur->left;
				}
				else return cur;

			}
			return nullptr;
		}

		//插入
		bool Insert(const pair<K,V>& kv) {
			if (_root == nullptr) {
				_root = new Node(kv);
				return true;
			}

			pNode cur = _root;
			pNode pa = nullptr;
			while (cur) {
				if (cur->_kv.first < kv.first) {
					pa = cur;
					cur = cur->right;
				}
				else if (cur->_kv.first > kv.first) {
					pa = cur;
					cur = cur->left;
				}
				else return false;//已经存在无需插入

			}
			cur = new Node(kv);
			if (pa->_kv.first >kv.first ) {
				pa->left = cur;
			}
			else {
				pa->right = cur;
			}
			cur->father = pa;
			//更新平衡因子
			while (pa) {
				if (cur == pa->left) {
					pa->_bf--;
				}
				else {
					pa->_bf++;
				}

				if (pa->_bf == 0) {
					break;
				}

				else if (pa->_bf == 1 || pa->_bf == -1) {
					cur = pa;
					pa = pa->father;
				}
				else if (pa->_bf == -2 || pa->_bf == 2) {
					//需要调整，一共有四种调整方案
					if (pa->_bf == -2 && cur->_bf == -1) {
						//右单旋
						RotateR(pa);
					}
					else if (pa->_bf == 2 && cur->_bf == 1) {
						//左单旋
						RotateL(pa);
					}
					else if (pa->_bf == -2 && cur->_bf == 1) {
						RotateLR(pa);
					}
					else if (pa->_bf == 2 && cur->_bf == -1) {
						RotateRL(pa);
					}
					else {
						break;
					}
					break;
				}


			}

		}
		//遍历
		void InOrder() {
			_InOrder(_root);
			cout << endl;
		}
		//旋转
		//右单旋
		void RotateR(pNode pa) {
			pNode subL = pa->left;
			pNode subLR = subL->right;

			pa->left = subLR;
			if (subLR) subLR->father = pa;

			subL->right = pa;
			pNode ppa = pa->father;
			pa->father = subL;
			
			if (pa == _root) {
				_root = subL;
				subL->father = nullptr;
			}
			else {
				if (pa == ppa->left) {
					ppa->left = subL;
				}
				else {
					ppa->right = subL;
				}
				subL->father = ppa;
			}

			subL->_bf = pa->_bf = 0;
		}

		//左单旋
		void RotateL(pNode pa) {
			pNode subR = pa->right;
			pNode subRL = subR->left;

			pa->right = subRL;
			if (subRL) subRL->father = pa;

			subR->left = pa;
			pNode ppa = pa->father;
			pa->father = subR;

			if (pa == _root) {
				_root = subR;
				subR->father = nullptr;
			}
			else {
				if (pa == ppa->left) {
					ppa->left = subR;
				}
				else {
					ppa->right = subR;
				}
				subR->father = ppa;
			}

			subR->_bf = pa->_bf = 0;
		}
		//右左双旋
		void RotateRL(pNode pa) {
			pNode subR = pa->right;
			pNode subRL = subR->left;

			int subRL_bf =subRL->_bf;

			RotateR(subR);
			RotateL(pa);

			if (subRL_bf == -1) {
				pa->_bf = 0;
				subR->_bf = 1;
			}
			else if (subRL_bf == 1) {
				pa->_bf = -1;
				subR->_bf = 0;
			}
			else if (subRL_bf == 0) {
				pa->_bf = 0;
				subR->_bf = 0;
			}
			else {
				//perror("RotateRL");
			}
			subRL->_bf=0;

		}
		//左右双旋
		void RotateLR(pNode pa) {
			pNode subL = pa->left;
			pNode subLR = subL->right;

			int subLR_bf = subLR->_bf;

			RotateL(subL);
			RotateR(pa);

			if (subLR_bf == -1) {
				pa->_bf = 1 ;
				subL->_bf = 0;
			}
			else if (subLR_bf == 1) {
				pa->_bf = 0;
				subL->_bf = -1;
			}
			else if (subLR_bf == 0) {
				pa->_bf = 0;
				subL->_bf = 0;
			}
			else {
				//perror("RotateLR");
			}
			subLR->_bf=0;
			return;
		}


	private:
		void _InOrder(pNode root) {
			if (root == nullptr)return;
			_InOrder(root->left);
			cout << root->_kv.first << " " << root->_kv.second << endl;
			_InOrder(root->right);
		}
		pNode _root;
	};
};